#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>


 struct ListNode 
 {
    int val;
    struct ListNode *next; 
 };


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	struct ListNode* phead, *tail;
	phead = tail = NULL;
	while (list1&&list2)
	{
		if (list1->val<list2->val)
		{
			if (phead == NULL)
			{
				phead = tail = list1;
			}
			else
			{
				tail->next = list1;
			}
			list1 = list1->next;
		}
		else
		{
			if (phead == NULL)
			{
				phead = tail = list2;
			}
			else
			{
				tail->next = list2;
			}
			list2 = list2->next;
		}
	}
	if (list1 == NULL)
	{
		tail->next = list2;
	}
	else
	{
		tail->next = list1;
	}
	return phead;
}